package tulingxueyuan117;

import java.util.HashMap;
import java.util.Map;

/**
 * Author: Zhang Dongwei
 * Date: 2022/4/5 19:06
 * 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
 *
 * 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
 */
public class p5_爬楼梯_70 {
    public static void main(String[] args) {
        int n = 6;
        int res = climbStairs(n);
        System.out.println(res);
    }

    // 递归算法，LeetCode超时，时间复杂度为O(2^n)
    public static int climbStairs1(int n) {
        if(n <= 0){
            return 0;
        }if(n == 1){
            return 1;
        }else if(n == 2){
            return 2;
        }else return climbStairs(n-1) + climbStairs(n-2);
    }

    // 引入hashmap, 时间复杂度为O(n)
    private static Map<Integer, Integer> storeMap = new HashMap<>();
    public static int climbStairs2(int n) {
        if(n == 1) return 1;
        if(n == 2) return 2;
        if(null != storeMap.get(n)) return storeMap.get(n);
        else {
            int result = climbStairs(n-1) + climbStairs(n - 2);
            storeMap.put(n, result);
            return result;
        }
    }

    // 上面两种方法是自顶向下，使用循环自底向上累加, 时间复杂度为O(n)
    public static int climbStairs(int n){
        if(n == 1) return 1;
        if(n == 2) return 2;
        int result = 0;
        int pre = 2; // 前面第一个，即climbStairs(n-1)
        int prePre = 1; // 前面第二个，即climbStairs(n-2)
        for(int i = 3; i <= n; i++){
            result = pre + prePre;
            prePre = pre;
            pre = result;
        }
        return result;
    }
}
